Characteristic polynomials of p-adic matrices
Identifieur interne : 000029 ( Main/Exploration ); précédent : 000028; suivant : 000030Characteristic polynomials of p-adic matrices
Auteurs : Xavier Caruso [France] ; David Roe [États-Unis] ; Tristan Vaccon [France]Source :
English descriptors
Abstract
We analyze the precision of the characteristic polynomial of an n×n p-adic matrix A using differential precision methods developed previously. When A is integral with precision O(p^N), we give a criterion (checkable in time O˜(n^omega)) for χ(A) to have precision exactly O(p^N). We also give a O˜(n^3) algorithm for determining the optimal precision when the criterion is not satisfied, and give examples when the precision is larger than O(p^N).
Url:
Affiliations:
- France, États-Unis
- Limousin, Pennsylvanie, Région Bretagne
- Limoges, Pittsburgh, Rennes
- Université de Limoges, Université de Pittsburgh, Université de Rennes 1, Université européenne de Bretagne
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 000124
- to stream Hal, to step Curation: 000124
- to stream Hal, to step Checkpoint: 000029
- to stream Main, to step Merge: 000029
- to stream Main, to step Curation: 000029
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Characteristic polynomials of p-adic matrices</title>
<author><name sortKey="Caruso, Xavier" sort="Caruso, Xavier" uniqKey="Caruso X" first="Xavier" last="Caruso">Xavier Caruso</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-75" status="VALID"> <idno type="IdRef">028233107</idno>
<idno type="ISNI">0000 0001 2186 8595 </idno>
<idno type="RNSR">199612396W</idno>
<orgName>Institut de Recherche Mathématique de Rennes</orgName>
<orgName type="acronym">IRMAR</orgName>
<date type="start">1996</date>
<desc> <address> <addrLine>Campus de Beaulieu, bâtiments 22 et 23, 263 avenue du Général Leclerc, CS 7420535042 RENNES Cédex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://irmar.univ-rennes1.fr/</ref>
</desc>
<listRelation> <relation active="#struct-105160" type="direct"></relation>
<relation active="#struct-108028" type="direct"></relation>
<relation active="#struct-247362" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation name="- RENNES" active="#struct-301232" type="direct"></relation>
<relation active="#struct-406201" type="direct"></relation>
<relation name="UMR6625" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-105160" type="direct"><org type="institution" xml:id="struct-105160" status="VALID"> <orgName>Université de Rennes 1</orgName>
<orgName type="acronym">UR1</orgName>
<desc> <address> <addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rennes1.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-108028" type="direct"><org type="institution" xml:id="struct-108028" status="VALID"> <orgName>AGROCAMPUS OUEST</orgName>
<desc> <address> <addrLine>Institut Supérieur des Sciences Agronomiques, Agroalimentaires, Horticoles et du Paysage - 65, rue de St Brieuc - CS 84215 - 35042 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.agrocampus-ouest.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-247362" type="direct"><org type="institution" xml:id="struct-247362" status="VALID"> <orgName>École normale supérieure - Rennes</orgName>
<orgName type="acronym">ENS Rennes</orgName>
<desc> <address> <addrLine>Campus de Ker Lann - avenue Robert Schuman - 35170 Bruz</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ens-rennes.fr</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle name="- RENNES" active="#struct-301232" type="direct"><org type="institution" xml:id="struct-301232" status="VALID"> <orgName>Institut National des Sciences Appliquées</orgName>
<orgName type="acronym">INSA</orgName>
<desc> <address> <country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-406201" type="direct"><org type="institution" xml:id="struct-406201" status="VALID"> <orgName>Université de Rennes 2</orgName>
<orgName type="acronym">UR2</orgName>
<desc> <address> <addrLine>Place du recteur Henri Le Moal - CS 24307 - 35043 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rennes2.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR6625" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"> <idno type="IdRef">02636817X</idno>
<idno type="ISNI">0000000122597504</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc> <address> <country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Rennes</settlement>
<region type="region" nuts="2">Région Bretagne</region>
</placeName>
<orgName type="university">Université de Rennes 1</orgName>
<orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName>
</affiliation>
</author>
<author><name sortKey="Roe, David" sort="Roe, David" uniqKey="Roe D" first="David" last="Roe">David Roe</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-184330" status="VALID"> <orgName>University of Pittsburgh [Pittsburg]</orgName>
<desc> <address> <addrLine>4200 Fifth Avenue Pittsburgh, PA 15260</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.pitt.edu/</ref>
</desc>
<listRelation> <relation active="#struct-378064" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-378064" type="direct"><org type="institution" xml:id="struct-378064" status="INCOMING"> <orgName>University of Pittsburgh</orgName>
<desc> <address> <country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Pittsburgh</settlement>
<region type="state">Pennsylvanie</region>
</placeName>
<orgName type="university">Université de Pittsburgh</orgName>
</affiliation>
</author>
<author><name sortKey="Vaccon, Tristan" sort="Vaccon, Tristan" uniqKey="Vaccon T" first="Tristan" last="Vaccon">Tristan Vaccon</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-444304" status="VALID"><orgName>Mathématiques & Sécurité de l'information</orgName>
<orgName type="acronym">XLIM-MATHIS</orgName>
<date type="start">2016-01-01</date>
<desc><address><addrLine>XLIM - 123, avenue Albert Thomas - 87060 LIMOGES CEDEX</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.xlim.fr/</ref>
</desc>
<listRelation><relation name="MATHIS" active="#struct-182467" type="direct"></relation>
<relation name="UMR7252" active="#struct-5928" type="indirect"></relation>
<relation name="UMR7252" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle name="MATHIS" active="#struct-182467" type="direct"><org type="laboratory" xml:id="struct-182467" status="VALID"><idno type="IdRef">128007052</idno>
<idno type="ISNI">0000000405977726</idno>
<idno type="RNSR">201220195D</idno>
<orgName>XLIM</orgName>
<orgName type="acronym">XLIM</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>123 Avenue Albert THOMAS 87060 LIMOGES CEDEX</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.xlim.fr</ref>
</desc>
<listRelation><relation name="UMR7252" active="#struct-5928" type="direct"></relation>
<relation name="UMR7252" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7252" active="#struct-5928" type="indirect"><org type="institution" xml:id="struct-5928" status="VALID"><idno type="IdRef">026403315</idno>
<idno type="ISNI">0000000121654861</idno>
<orgName>Université de Limoges</orgName>
<orgName type="acronym">UNILIM</orgName>
<date type="start">1968-10-01</date>
<desc><address><addrLine>33 rue François Mitterrand BP23204 87032 Limoges</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.unilim.fr</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7252" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"> <idno type="IdRef">02636817X</idno>
<idno type="ISNI">0000000122597504</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc> <address> <country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Limoges</settlement>
<region type="region" nuts="2">Limousin</region>
</placeName>
<orgName type="university">Université de Limoges</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-01458027</idno>
<idno type="halId">hal-01458027</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-01458027</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-01458027</idno>
<date when="2017-02-06">2017-02-06</date>
<idno type="wicri:Area/Hal/Corpus">000124</idno>
<idno type="wicri:Area/Hal/Curation">000124</idno>
<idno type="wicri:Area/Hal/Checkpoint">000029</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000029</idno>
<idno type="wicri:Area/Main/Merge">000029</idno>
<idno type="wicri:Area/Main/Curation">000029</idno>
<idno type="wicri:Area/Main/Exploration">000029</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Characteristic polynomials of p-adic matrices</title>
<author><name sortKey="Caruso, Xavier" sort="Caruso, Xavier" uniqKey="Caruso X" first="Xavier" last="Caruso">Xavier Caruso</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-75" status="VALID"> <idno type="IdRef">028233107</idno>
<idno type="ISNI">0000 0001 2186 8595 </idno>
<idno type="RNSR">199612396W</idno>
<orgName>Institut de Recherche Mathématique de Rennes</orgName>
<orgName type="acronym">IRMAR</orgName>
<date type="start">1996</date>
<desc> <address> <addrLine>Campus de Beaulieu, bâtiments 22 et 23, 263 avenue du Général Leclerc, CS 7420535042 RENNES Cédex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://irmar.univ-rennes1.fr/</ref>
</desc>
<listRelation> <relation active="#struct-105160" type="direct"></relation>
<relation active="#struct-108028" type="direct"></relation>
<relation active="#struct-247362" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation name="- RENNES" active="#struct-301232" type="direct"></relation>
<relation active="#struct-406201" type="direct"></relation>
<relation name="UMR6625" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-105160" type="direct"><org type="institution" xml:id="struct-105160" status="VALID"> <orgName>Université de Rennes 1</orgName>
<orgName type="acronym">UR1</orgName>
<desc> <address> <addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rennes1.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-108028" type="direct"><org type="institution" xml:id="struct-108028" status="VALID"> <orgName>AGROCAMPUS OUEST</orgName>
<desc> <address> <addrLine>Institut Supérieur des Sciences Agronomiques, Agroalimentaires, Horticoles et du Paysage - 65, rue de St Brieuc - CS 84215 - 35042 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.agrocampus-ouest.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-247362" type="direct"><org type="institution" xml:id="struct-247362" status="VALID"> <orgName>École normale supérieure - Rennes</orgName>
<orgName type="acronym">ENS Rennes</orgName>
<desc> <address> <addrLine>Campus de Ker Lann - avenue Robert Schuman - 35170 Bruz</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ens-rennes.fr</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle name="- RENNES" active="#struct-301232" type="direct"><org type="institution" xml:id="struct-301232" status="VALID"> <orgName>Institut National des Sciences Appliquées</orgName>
<orgName type="acronym">INSA</orgName>
<desc> <address> <country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-406201" type="direct"><org type="institution" xml:id="struct-406201" status="VALID"> <orgName>Université de Rennes 2</orgName>
<orgName type="acronym">UR2</orgName>
<desc> <address> <addrLine>Place du recteur Henri Le Moal - CS 24307 - 35043 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rennes2.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR6625" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"> <idno type="IdRef">02636817X</idno>
<idno type="ISNI">0000000122597504</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc> <address> <country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Rennes</settlement>
<region type="region" nuts="2">Région Bretagne</region>
</placeName>
<orgName type="university">Université de Rennes 1</orgName>
<orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName>
</affiliation>
</author>
<author><name sortKey="Roe, David" sort="Roe, David" uniqKey="Roe D" first="David" last="Roe">David Roe</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-184330" status="VALID"> <orgName>University of Pittsburgh [Pittsburg]</orgName>
<desc> <address> <addrLine>4200 Fifth Avenue Pittsburgh, PA 15260</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.pitt.edu/</ref>
</desc>
<listRelation> <relation active="#struct-378064" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-378064" type="direct"><org type="institution" xml:id="struct-378064" status="INCOMING"> <orgName>University of Pittsburgh</orgName>
<desc> <address> <country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Pittsburgh</settlement>
<region type="state">Pennsylvanie</region>
</placeName>
<orgName type="university">Université de Pittsburgh</orgName>
</affiliation>
</author>
<author><name sortKey="Vaccon, Tristan" sort="Vaccon, Tristan" uniqKey="Vaccon T" first="Tristan" last="Vaccon">Tristan Vaccon</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-444304" status="VALID"><orgName>Mathématiques & Sécurité de l'information</orgName>
<orgName type="acronym">XLIM-MATHIS</orgName>
<date type="start">2016-01-01</date>
<desc><address><addrLine>XLIM - 123, avenue Albert Thomas - 87060 LIMOGES CEDEX</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.xlim.fr/</ref>
</desc>
<listRelation><relation name="MATHIS" active="#struct-182467" type="direct"></relation>
<relation name="UMR7252" active="#struct-5928" type="indirect"></relation>
<relation name="UMR7252" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle name="MATHIS" active="#struct-182467" type="direct"><org type="laboratory" xml:id="struct-182467" status="VALID"><idno type="IdRef">128007052</idno>
<idno type="ISNI">0000000405977726</idno>
<idno type="RNSR">201220195D</idno>
<orgName>XLIM</orgName>
<orgName type="acronym">XLIM</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>123 Avenue Albert THOMAS 87060 LIMOGES CEDEX</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.xlim.fr</ref>
</desc>
<listRelation><relation name="UMR7252" active="#struct-5928" type="direct"></relation>
<relation name="UMR7252" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7252" active="#struct-5928" type="indirect"><org type="institution" xml:id="struct-5928" status="VALID"><idno type="IdRef">026403315</idno>
<idno type="ISNI">0000000121654861</idno>
<orgName>Université de Limoges</orgName>
<orgName type="acronym">UNILIM</orgName>
<date type="start">1968-10-01</date>
<desc><address><addrLine>33 rue François Mitterrand BP23204 87032 Limoges</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.unilim.fr</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7252" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"> <idno type="IdRef">02636817X</idno>
<idno type="ISNI">0000000122597504</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc> <address> <country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Limoges</settlement>
<region type="region" nuts="2">Limousin</region>
</placeName>
<orgName type="university">Université de Limoges</orgName>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Algorithms</term>
<term>characteristic polynomial</term>
<term>eigenvalue</term>
<term>p-adic precision</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We analyze the precision of the characteristic polynomial of an n×n p-adic matrix A using differential precision methods developed previously. When A is integral with precision O(p^N), we give a criterion (checkable in time O˜(n^omega)) for χ(A) to have precision exactly O(p^N). We also give a O˜(n^3) algorithm for determining the optimal precision when the criterion is not satisfied, and give examples when the precision is larger than O(p^N).</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>États-Unis</li>
</country>
<region><li>Limousin</li>
<li>Pennsylvanie</li>
<li>Région Bretagne</li>
</region>
<settlement><li>Limoges</li>
<li>Pittsburgh</li>
<li>Rennes</li>
</settlement>
<orgName><li>Université de Limoges</li>
<li>Université de Pittsburgh</li>
<li>Université de Rennes 1</li>
<li>Université européenne de Bretagne</li>
</orgName>
</list>
<tree><country name="France"><region name="Région Bretagne"><name sortKey="Caruso, Xavier" sort="Caruso, Xavier" uniqKey="Caruso X" first="Xavier" last="Caruso">Xavier Caruso</name>
</region>
<name sortKey="Vaccon, Tristan" sort="Vaccon, Tristan" uniqKey="Vaccon T" first="Tristan" last="Vaccon">Tristan Vaccon</name>
</country>
<country name="États-Unis"><region name="Pennsylvanie"><name sortKey="Roe, David" sort="Roe, David" uniqKey="Roe D" first="David" last="Roe">David Roe</name>
</region>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000029 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000029 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Amérique |area= PittsburghV1 |flux= Main |étape= Exploration |type= RBID |clé= Hal:hal-01458027 |texte= Characteristic polynomials of p-adic matrices }}
This area was generated with Dilib version V0.6.38. |